3.1_循环群与对称群_循环群与初等数论.2.ZH解释

本段旨在为后续讨论建立清晰的符号约定，以简化在群 $\mathbb{Z} / n \mathbb{Z}$ 中的书写。

1. 省略方括号：$\mathbb{Z} / n \mathbb{Z}$ 是一个由同余类组成的群。一个同余类 $[a]_n$ 是所有与整数 $a$ 模 $n$ 同余的整数的集合，即 $\{..., a-2n, a-n, a, a+n, a+2n, ...\}$。为了书写方便，在上下文清晰、不会引起混淆的情况下，我们常常直接用整数 $a$ 来代表它所在的同余类 $[a]_n$。例如，在 $\mathbb{Z} / 6 \mathbb{Z}$ 中，我们可能会直接写 $2$ 来表示集合 $\{..., -10, -4, 2, 8, 14, ...\}$。
2. 保留方括号的场景：在两种情况下，我们必须明确写出方括号 $[\cdot]_n$ 以避免歧义：
   • 区分整数与同余类：当我们想同时讨论一个整数 $a$ 和它在 $\mathbb{Z} / n \mathbb{Z}$ 中对应的同余类 $[a]_n$ 时。例如，比较整数 $6$ 和同余类 $[6]_5 = [1]_5$。
   • 区分不同模数的同余类：当一个整数 $a$ 可能被看作是不同群 $\mathbb{Z} / n \mathbb{Z}$ 和 $\mathbb{Z} / m \mathbb{Z}$ 中的元素时。例如，整数 $3$ 在 $\mathbb{Z} / 5 \mathbb{Z}$ 中是 $[3]_5$，在 $\mathbb{Z} / 4 \mathbb{Z}$ 中是 $[3]_4$。这两个是完全不同的数学对象。
3. 两种代数运算：在集合 $\mathbb{Z} / n \mathbb{Z}$ 上，我们可以定义两种运算：
   • 加法：$[a]_n + [b]_n = [a+b]_n$。这个运算使得 $(\mathbb{Z} / n \mathbb{Z}, +)$ 构成一个阿贝尔群（循环群）。
   • 乘法：$[a]_n \cdot [b]_n = [ab]_n$。这个运算使得 $(\mathbb{Z} / n \mathbb{Z}, \cdot)$ 构成一个交换幺半群（有单位元 $[1]_n$，但不一定每个元素都有逆元）。
4. 乘法与“指数”记法的关系：公式 $[a]_{n}[b]_{n}=[a b]_{n}=a \cdot[b]_{n}=b \cdot[a]_{n}$ 揭示了两种看似不同但结果相同的计算方式。
   • $[a]_n[b]_n$ 是在环 $\mathbb{Z} / n \mathbb{Z}$ 中的乘法。
   • $a \cdot [b]_n$ 是一个记法上的简写，它表示在加法群 $(\mathbb{Z} / n \mathbb{Z}, +)$ 中，将元素 $[b]_n$ 与自身相加 $a$ 次。这类似于群论中一般的“指数”记法 $g^a$，只不过因为这里的运算是加法，所以写成了乘法形式 $a \cdot g$。例如，如果 $a=3$，则 $3 \cdot [b]_n = [b]_n + [b]_n + [b]_n$。

这一段是引言，预告了接下来要讨论的核心问题：在模算术的世界里，形如 $ax=b$ 的线性方程是否有解。

1. 问题的提出: 我们在初等代数中熟悉的线性方程是 $ax=b$，在实数范围内，只要 $a \ne 0$，解就是 $x=b/a$。但在 $\mathbb{Z} / n \mathbb{Z}$ 这个有限的、离散的结构中，情况要复杂得多。“除法”并不总是可行。因此，我们需要一个明确的“判别准则”来判断何时可以找到一个元素 $x$ 满足方程。
2. 两种等价的表述:
   • $\mathbb{Z} / n \mathbb{Z}$ 中的方程 $ax=b$: 这里的 $a, b, x$ 都是 $\mathbb{Z} / n \mathbb{Z}$ 中的同余类。例如，在 $\mathbb{Z} / 6 \mathbb{Z}$ 中解方程 $2x=4$。我们发现 $x=2$ 是一个解，因为 $2 \cdot 2 = 4$。$x=5$ 也是一个解，因为 $2 \cdot 5 = 10 \equiv 4 \pmod 6$。而方程 $2x=3$ 在 $\mathbb{Z} / 6 \mathbb{Z}$ 中则没有解。
   • 整数中的同余方程 $ax \equiv b \pmod n$: 这里的 $a, b, n$ 是整数，我们寻找一个整数解 $x$。这个方程的含义是“$ax$ 和 $b$ 除以 $n$ 的余数相同”，或者说“$ax-b$ 是 $n$ 的倍数”。

这两个问题是完全等价的。如果整数 $x_0$ 是 $ax \equiv b \pmod n$ 的一个解，那么同余类 $[x_0]_n$ 就是 $\mathbb{Z} / n \mathbb{Z}$ 中方程 $[a]_n x = [b]_n$ 的一个解。反之亦然。所以，研究其中一个，就等于研究了另一个。

1. “首先，有以下观察”: 这句话告诉我们，为了解决这个核心问题，我们需要先建立一些基础性的事实和引理。这些观察将作为后续定理的基石。

这个引理建立了整数的整除性与 $\mathbb{Z} / n \mathbb{Z}$ 中同余类的子群生成之间的重要联系。它是后续所有结论的基石。让我们逐条拆解。

(i) $d \mid a \Longleftrightarrow[a]_{n} \in\left\langle[d]_{n}\right\rangle$

• 含义: 这条说的是，一个整数 $a$ 能被 $n$ 的约数 $d$ 整除，这件事情等价于， $a$ 对应的同余类 $[a]_n$ 属于由 $d$ 对应的同余类 $[d]_n$ 在加法群 $(\mathbb{Z} / n \mathbb{Z}, +)$ 中生成的循环子群 $\langle[d]_n\rangle$。
• 什么是 $\langle[d]_n\rangle$？ 它是由 $[d]_n$ 生成的循环子群，其元素是通过重复地将 $[d]_n$ 与自身相加得到的所有可能结果。即 $\langle[d]_n\rangle = \{k \cdot [d]_n \mid k \in \mathbb{Z}\} = \{[kd]_n \mid k \in \mathbb{Z}\}$。这个集合包含了 $[0]_n, [d]_n, [2d]_n, ..., [(n/d-1)d]_n$。
• 所以 (i) 说的就是： $d$ 整除 $a$ 当且仅当 $[a]_n$ 可以被表示为 $[kd]_n$ 的形式，其中 $k$ 是某个整数。
• 证明的直观理解:
• ($\Longrightarrow$): 如果 $d$ 整除 $a$，意味着 $a = k d$ 对于某个整数 $k$。那么在 $\mathbb{Z} / n \mathbb{Z}$ 中，它们的同余类也相等：$[a]_n = [kd]_n$。根据循环子群的定义，$[kd]_n$ 正是 $[d]_n$ 的 $k$ 倍，所以 $[a]_n$ 必然在 $\langle[d]_n\rangle$ 里。
• ($\Longleftarrow$): 如果 $[a]_n \in \langle[d]_n\rangle$，意味着 $[a]_n$ 可以写成某个 $[d]_n$ 的倍数，即 $[a]_n = k \cdot [d]_n = [kd]_n$。两个同余类相等，意味着它们对应的整数 $a$ 和 $kd$ 模 $n$ 同余，即 $a \equiv kd \pmod n$。这说明 $a - kd$ 是 $n$ 的倍数，即 $a - kd = \ell n$ 对某个整数 $\ell$。变形得到 $a = kd + \ell n$。因为 $d$ 是 $n$ 的约数，所以 $d$ 能整除 $n$，从而 $d$ 能整除 $\ell n$。显然 $d$ 也能整除 $kd$。因此 $d$ 必然能整除它们的和 $kd + \ell n$，即 $d \mid a$。

(ii) $a \equiv a^{\prime} \bmod n \implies (d|a \Longleftrightarrow d| a^{\prime})$

• 含义: 如果两个整数 $a$ 和 $a'$ 模 $n$ 同余（即它们属于同一个同余类），那么对于 $n$ 的任何一个约数 $d$，要么 $d$ 同时整除 $a$ 和 $a'$，要么 $d$ 同时不整除它们。
• 证明的直观理解: 既然 $a$ 和 $a'$ 属于同一个同余类，即 $[a]_n = [a']_n$。根据第 (i) 条结论，$d \mid a$ 等价于 $[a]_n \in \langle[d]_n\rangle$。同理，$d \mid a'$ 等价于 $[a']_n \in \langle[d]_n\rangle$。因为 $[a]_n = [a']_n$，所以这两个等价关系是联动的：$[a]_n$ 在不在 $\langle[d]_n\rangle$ 里，和 $[a']_n$ 在不在 $\langle[d]_n\rangle$ 里，是同一件事。所以 $d \mid a$ 和 $d \mid a'$ 也是同一件事。

(iii) $a \equiv a^{\prime} \bmod n \implies \operatorname{gcd}(a, n)=\operatorname{gcd}\left(a^{\prime}, n\right)$

• 含义: 同一个同余类中的所有整数，与模数 $n$ 的最大公约数是相同的。
• 证明的直观理解:
• $\operatorname{gcd}(a, n)$ 是 $a$ 和 $n$ 的所有公约数中最大的那个。
• 根据第 (ii) 条，如果 $a \equiv a' \pmod n$，那么对于 $n$ 的任何一个约数 $d$，都有 $d|a \Longleftrightarrow d|a'$。
• 这个结论可以推广到任何整数 $e$：$e$ 是 $a$ 和 $n$ 的公约数 $\iff$ $e \mid a$ 且 $e \mid n$。如果 $e \mid n$，那么 $e$ 是 $n$ 的一个约数。由(ii)可知 $e|a \iff e|a'$。因此，$e$ 是 $a$ 和 $n$ 的公约数 $\iff$ $e$ 是 $a'$ 和 $n$ 的公约数。
• 这意味着，集合 $\{e \in \mathbb{Z} \mid e \mid a \text{ and } e \mid n\}$ 和集合 $\{e \in \mathbb{Z} \mid e \mid a' \text{ and } e \mid n\}$ 是完全相同的。
• 两个完全相同的整数集合，它们的最大元素自然也相同。所以 $\operatorname{gcd}(a, n) = \operatorname{gcd}(a', n)$。

这个推论是引理 1.4.1(iii) 的直接应用，它正式确立了一个非常重要的概念：“同余类与模数的互素关系”。

1. “良定义函数” (Well-defined function): 在处理像同余类这样的集合对象时，“良定义”是一个至关重要的概念。一个从同余类集合 $\mathbb{Z} / n \mathbb{Z}$ 出发的函数 $f$，其输入是整个同余类 $[a]_n$，但其计算规则通常依赖于从这个类中选出的某个代表元 (representative) $a$。
   • 问题: 同余类 $[a]_n$ 中有无穷多个整数（如 $[2]_5 = \{..., -8, -3, 2, 7, 12, ...\}$）。如果函数 $f$ 的计算结果依赖于我们具体选了哪个代表元（例如，选 $2$ 和选 $7$ 算出来不一样），那么这个函数就是“病态的”或“非良定义的”，因为它对同一个输入（同余类 $[2]_5$）会给出不同的输出，这违反了函数的基本定义。
   • “良定义”的含义: 意味着无论你从同余类 $[a]_n$ 中挑选哪一个代表元 $a'$ 来计算 $f([a]_n)$，结果都是一样的。
2. $f\left([a]_{n}\right)=\operatorname{gcd}(a, n)$ 是良定义的:
   • 这个推论断言，我们定义一个函数 $f$，输入是一个同余类 $[a]_n$，输出是该同余类的代表元 $a$ 与模数 $n$ 的最大公约数。
   • 为什么它是良定义的？ 正是因为引理 1.4.1(iii)。该引理证明了：如果 $a \equiv a' \pmod n$（即 $a$ 和 $a'$ 是同一个同余类的两个不同代表元），那么 $\operatorname{gcd}(a, n) = \operatorname{gcd}(a', n)$。
   • 这意味着，无论你用 $a$ 还是 $a'$ 去计算最大公约数，得到的结果都完全相同。因此，将 $\operatorname{gcd}(a,n)$ 作为对整个同余类 $[a]_n$ 的一个属性是合理和一致的。这个函数是良定义的。
3. 互素关系的良定义性:
   • “$a$ 和 $n$ 互素”的定义是 $\operatorname{gcd}(a, n) = 1$。
   • 推论的后半部分是前半部分的一个特例。既然函数 $f([a]_n) = \operatorname{gcd}(a, n)$ 是良定义的，那么“$f([a]_n)$ 是否等于 $1$”这个问题也是良定义的。
   • 也就是说，如果 $a \equiv a' \pmod n$，那么 $\operatorname{gcd}(a, n) = 1 \Longleftrightarrow \operatorname{gcd}(a', n) = 1$。
   • 结论: 我们可以谈论一个同余类 $[a]_n$ 是否与 $n$ 互素，而不用担心这依赖于我们具体想的是哪个代表元 $a$。如果同余类中有一个元素与 $n$ 互素，那么该类中所有的元素都与 $n$ 互素。

这是一个简短的过渡段落，重申并确认了之前提到的符号简化约定。

1. 回到约定: 作者提醒读者，在建立了关于同余类与其代表元属性一致性的坚实基础（即推论 1.4.2）之后，现在可以安心地、更频繁地使用简写了。
2. 写成整数: 这就是指用整数 $a$ 来代替它所代表的同余类 $[a]_n$。例如，在讨论 $\mathbb{Z}/8\mathbb{Z}$ 中的元素时，直接写 $3, 5, 7$ 而不是 $[3]_8, [5]_8, [7]_8$。
3. 模糊区别: 这是一种坦诚的表述。作者承认，这种简写有时会“模糊”一个整数（一个数轴上的点）和一个同余类（一个无穷整数集合）之间的概念差异。然而，由于推论 1.4.2 保证了在很多重要属性（如与模数的 gcd）上这种模糊是无害的，所以为了表达的简洁性，这样做是值得的。这在数学中是常见的做法，即在确保严谨性的前提下，采用最经济的符号。

这个命题给出了我们在 1.1.2 节中提出的问题的第一个正式答案：线性同余方程 $ax=c$ 何时有解？

1. 命题解析:
   • 给定: $a$ 和 $c$ 是模 n 环 $\mathbb{Z} / n \mathbb{Z}$ 中的两个元素（同余类）。
   • 问题: 是否存在一个同余类 $x \in \mathbb{Z} / n \mathbb{Z}$，使得 $a$ 与 $x$ 的乘积等于 $c$？
   • 判别准则: 命题说，上述方程有解的充分必要条件是：同余类 $c$ 必须是循环子群 $\langle d \rangle$ 中的一个元素。
   • $d$ 是什么: 这里的 $d$ 是一个整数，它是 $a$ (的任意代表元) 与模数 $n$ 的最大公约数，即 $d = \operatorname{gcd}(a, n)$。
   • $\langle d \rangle$ 是什么: 这里的 $\langle d \rangle$ 是指由同余类 $[d]_n$ 在加法群 $(\mathbb{Z} / n \mathbb{Z}, +)$ 中生成的循环子群。它的元素是 $\{[0]_n, [d]_n, [2d]_n, ..., [(n/d-1)d]_n\}$。
2. 核心思想: 这个命题将乘法方程 $ax=c$ 的可解性问题，转化为了一个关于加法子群成员资格的判定问题。
   • 等式左边 $ax$ 能够产生的所有可能结果的集合，即 $\{ax \mid x \in \mathbb{Z}/n\mathbb{Z}\}$，其实就是由 $a$ 生成的主理想 $(a)$。
   • 命题实际上是在说：方程 $ax=c$ 有解 $\iff c$ 在 $a$ 生成的主理想里。
   • 而这个命题进一步揭示了这个主理想 $(a)$ 的一个更简单的结构：它就等于由 $\operatorname{gcd}(a, n)$ 生成的循环子群 $\langle d \rangle$。
   • 所以，问题最终归结为：$c$ 是否是 $d = \operatorname{gcd}(a,n)$ 的倍数（在模 $n$ 的意义下）？
3. 证明的剖析 (原文):
   • 第一步：翻译问题。
   • 将 $\mathbb{Z}/n\mathbb{Z}$ 中的方程 $ax=c$ 翻译回整数语言，就是寻找整数 $x$ 使得 $ax \equiv c \pmod n$。
   • 第二步：利用同余的定义。
   • $ax \equiv c \pmod n$ 意味着 $ax-c$ 是 $n$ 的倍数，即 $ax-c = -yn$ (原文用的 $yn$ 移项后是 $ax+ny=c$，本质一样)，或者说 $ax+ny=c$ 对于某个整数 $y$ 成立。
   • 第三步：应用裴蜀定理 (Bézout's Identity) 的推论。
   • 形如 $Ax+By=C$ 的丢番图方程有整数解 $(x, y)$ 的充分必要条件是 $\operatorname{gcd}(A, B)$ 必须整除 $C$。
   • 应用到我们的情况，$A=a, B=n, C=c$。所以方程 $ax+ny=c$ 有整数解 $(x, y)$ 的充要条件是 $\operatorname{gcd}(a, n)$ 整除 $c$。
   • 第四步：再次翻译回群论语言。
   • 令 $d = \operatorname{gcd}(a, n)$。我们得到了条件 $d \mid c$。
   • 根据我们刚刚学过的引理 1.4.1(i)，整数条件 $d \mid c$ 等价于同余类的条件 $[c]_n \in \langle [d]_n \rangle$。
   • 使用简化记法，就是 $c \in \langle d \rangle$。
   • 结论: 整个逻辑链条 $ax=c \text{ 有解} \iff ax \equiv c \pmod n \text{ 有解} \iff ax+ny=c \text{ 有解} \iff d \mid c \iff c \in \langle d \rangle$ 是一个完整的当且仅当 (if and only if) 的链条，证明完毕。

这个推论是前一个命题 1.4.3 的一个极其重要的特例。它完整地刻画了模 n 环中哪些元素具有乘法逆元。

1. 问题的特殊化: 我们现在关注的方程是 $ax=1$。这是在问：对于给定的元素 $a$，是否存在一个“倒数” $x$，使得它俩相乘的结果是乘法单位元 $1$。
   • 在环论中，满足这个条件的元素 $a$ 被称为可逆元 (invertible element) 或单位 (unit)。
2. 应用命题 1.4.3: 我们可以直接套用命题 1.4.3 的结论，只需将 $c$ 替换为 $1$。
   • 命题 1.4.3: $ax=c$ 有解 $\iff \operatorname{gcd}(a, n) \mid c$。
   • 应用到本推论: $ax=1$ 有解 $\iff \operatorname{gcd}(a, n) \mid 1$。
3. 结论的得出:
   • 一个正整数（$\operatorname{gcd}(a,n)$ 总是正的）能够整除 $1$，唯一的可能性就是这个正整数本身就是 $1$。
   • 因此，条件 $\operatorname{gcd}(a, n) \mid 1$ 等价于 $\operatorname{gcd}(a, n) = 1$。
   • $\operatorname{gcd}(a, n) = 1$ 的定义就是“整数 $a$ 和 $n$ 互素 (coprime 或 relatively prime)”。
   • 由于推论 1.4.2 保证了“互素”这个性质对于同余类是良定义的，我们可以说同余类 $a$ 与 $n$ 互素。
4. 总结: 一个元素 $a \in \mathbb{Z}/n\mathbb{Z}$ 是可逆元，当且仅当它所代表的整数与模数 $n$ 互素。

本段正式定义了核心研究对象之一：整数模 n 乘法群 $(\mathbb{Z} / n \mathbb{Z})^*$。

1. 定义回顾:
   • 首先，它提醒我们一个通用的代数概念：对于任何一个有乘法和单位元 1 的二元结构（如环或幺半群），我们用星号 * 来表示其所有可逆元的集合。
   • 因此，$(\mathbb{Z} / n \mathbb{Z})^*$ 就是 $\mathbb{Z} / n \mathbb{Z}$ 中所有具有乘法逆元的元素的集合。
2. 群的性质:
   • 这个可逆元的集合，在乘法运算下，自身也构成一个群。这在抽象代数中是一个普遍结论：
   • 封闭性: 两个可逆元的乘积仍然是可逆的 ($(ab)^{-1}=b^{-1}a^{-1}$) 。
   • 结合律: 继承自原来的结构 $(\mathbb{Z} / n \mathbb{Z}, \cdot)$。
   • 单位元: 原来的单位元 $1$ 总是可逆的，所以 $1 \in (\mathbb{Z} / n \mathbb{Z})^*$。
   • 逆元: 根据定义，集合里的每个元素都有逆元。
   • 此外，因为 $\mathbb{Z} / n \mathbb{Z}$ 的乘法是可交换的（$ab=ba$），所以 $(\mathbb{Z} / n \mathbb{Z})^*$ 的乘法也是可交换的，因此它是一个阿贝尔群。
3. 元素的具体刻画:
   • 结合推论 1.4.4，我们可以给出 $(\mathbb{Z} / n \mathbb{Z})^*$ 元素的精确描述。
   • 推论说可逆元等价于与 n 互素。
   • 因此，$(\mathbb{Z} / n \mathbb{Z})^*$ 的集合就是所有与模数 $n$ 互素的同余类的集合。这就是下面这个公式的含义。
4. 运算约定:
   • 当单独写出 $(\mathbb{Z} / n \mathbb{Z})^*$ 时，我们默认讨论的是它作为一个群的结构，并且其群运算是模 n 乘法，而不是加法。
5. 重要提醒:
   • $(\mathbb{Z} / n \mathbb{Z})^*$ 不是 $(\mathbb{Z} / n \mathbb{Z}, +)$ 的子群。这是一个非常重要的区分。
   • 子群的定义要求使用相同的运算。$(\mathbb{Z} / n \mathbb{Z}, +)$ 的运算是加法。
   • $(\mathbb{Z} / n \mathbb{Z})^*$ 的运算是乘法。运算都不同，根本谈不上是子群。
   • 而且，$(\mathbb{Z} / n \mathbb{Z})^*$ 对于加法通常是不封闭的。例如，在 $(\mathbb{Z} / 10 \mathbb{Z})^*$ 中，$3$ 和 $7$ 都是元素，但它们的和 $3+7=10 \equiv 0 \pmod{10}$，而 $0$ 并不在 $(\mathbb{Z} / 10 \mathbb{Z})^*$ 中。
   • $(\mathbb{Z} / n \mathbb{Z})^*$ 只是 $\mathbb{Z} / n \mathbb{Z}$ 的一个子集，它在另一种运算（乘法）下恰好构成了群。

这一段通过三个具体的例子，展示了不同类型的乘法群 $(\mathbb{Z}/n\mathbb{Z})^*$，并引入了对它们结构的初步分析，特别是“循环群”这个重要概念。

(i) $(\mathbb{Z} / 6 \mathbb{Z})^{*}$

• 元素: 我们要找与 $6$ 互素的数。在 $\{1, 2, 3, 4, 5\}$ 中，只有 $1$ 和 $5$ 与 $6$ 互素（$\operatorname{gcd}(1,6)=1, \operatorname{gcd}(5,6)=1$）。所以 $(\mathbb{Z} / 6 \mathbb{Z})^* = \{1, 5\}$。
• 群结构: 这个群只有 2 个元素。在群论中，任何一个 2 阶群（只有两个元素的群）都必然和循环群 $\mathbb{Z}/2\mathbb{Z}$ 同构（isomorphic）。同构意味着它们在结构上是完全一样的，只是元素的名字不同。
• $\mathbb{Z}/2\mathbb{Z} = \{0, 1\}$，运算是模 2 加法。
• $(\mathbb{Z}/6\mathbb{Z})^* = \{1, 5\}$，运算是模 6 乘法。
• 我们可以建立一个映射：$0 \mapsto 1$, $1 \mapsto 5$。这个映射保持了运算结构。
• 元素阶:
• $1$ 是单位元，阶为 $1$。
• $5$ 的阶是多少？我们要计算 $5$ 的幂次（模 6），直到结果为 $1$。$5^1 = 5 \pmod 6$。$5^2 = 25 \equiv 1 \pmod 6$。所以 $5$ 的阶是 $2$。

(ii) $(\mathbb{Z} / 5 \mathbb{Z})^{*}$

• 元素: 因为 $5$ 是素数，所以 $\{1, 2, 3, 4\}$ 都与 $5$ 互素。$(\mathbb{Z} / 5 \mathbb{Z})^* = \{1, 2, 3, 4\}$。
• 群的阶: 这个群的元素个数是 $4$，记为 $\#((\mathbb{Z} / 5 \mathbb{Z})^*)=4$。
• 循环群: 一个群被称为循环群，如果它能由其中一个元素（称为生成元）通过重复运算（这里是乘法）得到所有其他元素。
• 寻找生成元: 让我们来检验元素 $2$ 是否是生成元。
• $2^1 = 2 \pmod 5$
• $2^2 = 4 \pmod 5$
• $2^3 = 8 \equiv 3 \pmod 5$
• $2^4 = 16 \equiv 1 \pmod 5$
• 我们看到，$2$ 的幂次遍历了群里所有的元素 $\{2, 4, 3, 1\}$。因此，$2$ 是一个生成元，而 $(\mathbb{Z} / 5 \mathbb{Z})^*$ 是一个 4 阶循环群。我们可以记作 $(\mathbb{Z} / 5 \mathbb{Z})^* = \langle 2 \rangle$。

(iii) $(\mathbb{Z} / 8 \mathbb{Z})^{*}$

• 元素: 我们要找与 $8$ 互素的数。在 $\{1, ..., 7\}$ 中，只有奇数 $1, 3, 5, 7$ 与 $8$ 互素。$(\mathbb{Z} / 8 \mathbb{Z})^* = \{1, 3, 5, 7\}$。
• 群的阶: 这个群也有 4 个元素，$\#((\mathbb{Z} / 8 \mathbb{Z})^*)=4$。
• 是不是循环群？: 同样是 4 阶群，它和 $(\mathbb{Z} / 5 \mathbb{Z})^*$ 结构一样吗？我们来计算每个非单位元元素的阶。
• $3^1 = 3$, $3^2 = 9 \equiv 1 \pmod 8$。所以 $3$ 的阶是 $2$。它只能生成 $\{1, 3\}$，不能生成整个群。
• $5^1 = 5$, $5^2 = 25 \equiv 1 \pmod 8$。所以 $5$ 的阶是 $2$。它只能生成 $\{1, 5\}$。
• $7^1 = 7$, $7^2 = 49 \equiv 1 \pmod 8$。所以 $7$ 的阶是 $2$。它只能生成 $\{1, 7\}$。
• 结论: 这个群里，除了单位元 $1$ (阶为 1) 之外，所有其他元素的阶都是 $2$。没有任何一个元素的阶是 $4$ (群的阶)。根据循环群的定义，如果一个群是循环群，它必须有一个阶等于群的阶的元素（即生成元）。因为 $(\mathbb{Z} / 8 \mathbb{Z})^*$ 中没有 4 阶元素，所以它不是循环群。

这一段定义了一个在数论中极为重要的函数——欧拉 $\phi$ 函数 (Euler's totient function)。

1. 函数的定义:
   • 名称: 欧拉 $\phi$-函数，通常读作 "Euler's phi function"。
   • 符号: $\phi$ (希腊字母 phi)。
   • 定义域与值域: 它是一个从正整数集合 $\mathbb{N}$ (即 $\{1, 2, 3, ...\}$) 映射到正整数集合 $\mathbb{N}$ 的函数。即输入一个正整数 $n$，输出也是一个正整数 $\phi(n)$。
   • 核心定义: $\phi(n)$ 被定义为乘法群 $(\mathbb{Z} / n \mathbb{Z})^*$ 的阶 (order)，也就是这个群中元素的个数。符号 $\#(\cdot)$ 表示计算一个集合的元素数量。
2. 定义的等价解释:
   • 我们在 1.1.8 节中已经确定了 $(\mathbb{Z} / n \mathbb{Z})^*$ 的元素是什么：它们是所有与模数 $n$ 互素的同余类。
   • 在 $\mathbb{Z}/n\mathbb{Z}$ 中，我们通常用 $\{0, 1, ..., n-1\}$ 这 $n$ 个数作为所有同余类的代表元。
   • 因为推论 1.4.2保证了“互素”性质不依赖于代表元的选择，所以要计算 $(\mathbb{Z} / n \mathbb{Z})^*$ 的元素个数，我们只需要数一数在 $\{0, 1, ..., n-1\}$ 这组代表元中，有多少个数与 $n$ 互素。
   • (注意：$\operatorname{gcd}(0, n) = n$，所以 $0$ 只有在 $n=1$ 时才与 $n$ 互素。通常我们考虑 $n>1$，所以只需在 $\{1, ..., n-1\}$ 中计数即可。)
   • 因此，$\phi(n)$ 的计算方法就是：在从 1 到 n-1 (或 1 到 n) 的所有整数中，找出与 n 互素的数的个数。

这个命题给出了计算欧拉 $\phi$ 函数在一个重要情况下的具体公式：当输入是素数的幂时。

1. 简单情况：$\phi(p)$:
   • 命题: 如果 $p$ 是一个素数，那么 $\phi(p) = p-1$。
   • 解释: 根据 $\phi$ 函数的定义，$\phi(p)$ 是在 $\{1, 2, ..., p\}$ 中与 $p$ 互素的数的个数。
   • 因为 $p$ 是素数，它的约数只有 $1$ 和 $p$。
   • 所以，一个数要与 $p$ 不互素，它必须有除 $1$ 以外的公约数，这个公约数只能是 $p$。也就是说，这个数必须是 $p$ 的倍数。
   • 在 $\{1, 2, ..., p\}$ 这个集合里，唯一的 $p$ 的倍数就是 $p$ 本身。
   • 所以，总共 $p$ 个数中，只有 $p$ 这一个数与 $p$ 不互素。剩下的 $p-1$ 个数（即 $1, 2, ..., p-1$）都与 $p$ 互素。
   • 因此，$\phi(p) = p-1$。
2. 一般情况：$\phi(p^k)$:
   • 命题: 如果 $p$ 是素数且 $k$ 是正整数，那么 $\phi(p^k) = p^k - p^{k-1} = p^{k-1}(p-1)$。
   • 解释: 我们要计算在 $\{1, 2, ..., p^k\}$ 中与 $p^k$ 互素的数的个数。
   • 反向思考 (Inclusion-Exclusion Principle): 直接数互素的数比较困难，我们可以数不互素的数，然后用总数减去它。
   • 一个数 $a$ 与 $p^k$ 不互素意味着什么？$\operatorname{gcd}(a, p^k) > 1$。
   • 因为 $p^k$ 的所有约数都是 $p$ 的幂（$p, p^2, ...$），所以 $a$ 与 $p^k$ 有大于 1 的公约数，当且仅当它们有公素因子 $p$。
   • 也就是说，$a$ 与 $p^k$ 不互素 $\iff p$ 整除 $a$ ($\iff a$ 是 $p$ 的倍数)。
   • 现在问题转化为：在 $\{1, 2, ..., p^k\}$ 这个集合里，有多少个数是 $p$ 的倍数？
   • 这些数是：$p, 2p, 3p, ..., (p^{k-1})p$。
   • 最后一个数是 $p^{k-1} \cdot p = p^k$。所以总共有 $p^{k-1}$ 个 $p$ 的倍数。
   • 计算结果:
   • 总数：$p^k$
   • 不互素的数的数量：$p^{k-1}$
   • 互素的数的数量 = 总数 - 不互素的数的数量
   • $\phi(p^k) = p^k - p^{k-1}$。
   • 提取公因子 $p^{k-1}$，得到 $\phi(p^k) = p^{k-1}(p-1)$。

• 验证: 当 $k=1$ 时，公式变为 $\phi(p^1) = p^{1-1}(p-1) = p^0(p-1) = 1 \cdot (p-1) = p-1$。与简单情况一致。

这一段给出了 $\phi(n)$ 函数的一些基本性质和前几个值的示例，以帮助读者建立对该函数的直观感受。

1. $\phi(n)$ 的范围:
   • 对于 $n>1$，$\phi(n)$ 的值总是在 $1$ 和 $n-1$ 之间（包含两端）。
   • 为什么 $\phi(n) \ge 1$？ 因为对于任何 $n>1$，整数 $1$ 总是与 $n$ 互素的 ($\operatorname{gcd}(1, n)=1$)。所以至少有 $1$ 这一个数，保证了 $\phi(n) \ge 1$。
   • 为什么 $\phi(n) \le n-1$？ 因为整数 $n$ 本身与 $n$ 不互素 ($\operatorname{gcd}(n, n)=n$)。所以在 $\{1, ..., n\}$ 这 $n$ 个数中，至少有一个数 ($n$) 被排除掉了，所以最多剩下 $n-1$ 个。
2. $\phi(n) = n-1$ 的情况:
   • 这是一个非常特殊的情况，它成为一个判断素数的充分必要条件。
   • ($\Longleftarrow$) 如果 n 是素数: 我们在命题 1.4.7 中已经证明了 $\phi(n) = n-1$。
   • ($\Longrightarrow$) 如果 $\phi(n) = n-1$: 这意味着在 $\{1, 2, ..., n-1\}$ 这 $n-1$ 个数中，所有的数都与 $n$ 互素。如果 $n$ 是一个合数，那么它可以被分解为 $n=ab$，其中 $1 < a, b < n$。那么 $a$ 就是 $\{1, ..., n-1\}$ 中的一个数，但 $\operatorname{gcd}(a, n) = a > 1$，所以 $a$ 与 $n$ 不互素。这与“所有数都互素”的假设矛盾。因此，$n$ 必须是素数。
3. $\phi$ 函数值表格:
   • 这个表格列出了从 $n=1$ 到 $n=12$ 的 $\phi(n)$ 的值。它是一个方便的参考，也让我们能观察到一些规律。
   • $\phi(1)=1$: 与 1 互素的只有 1。
   • $\phi(2)=1$: 与 2 互素的只有 1。
   • $\phi(3)=2$: 与 3 互素的有 1, 2。
   • $\phi(4)=2$: 与 4 互素的有 1, 3。（应用公式 $\phi(2^2) = 2^1(2-1)=2$）
   • $\phi(5)=4$: 与 5 互素的有 1, 2, 3, 4。
   • $\phi(6)=2$: 与 6 互素的有 1, 5。
   • $\phi(7)=6$: 与 7 互素的有 1, 2, 3, 4, 5, 6。
   • $\phi(8)=4$: 与 8 互素的有 1, 3, 5, 7。（应用公式 $\phi(2^3)=4$）
   • $\phi(9)=6$: 与 9 互素的有 1, 2, 4, 5, 7, 8。（应用公式 $\phi(3^2)=6$）
   • $\phi(10)=4$: 与 10 互素的有 1, 3, 7, 9。
   • $\phi(11)=10$: 11 是素数。
   • $\phi(12)=4$: 与 12 互素的有 1, 5, 7, 11。

这个定理是本节的核心，它像一份“完全使用手册”，详细说明了加法群 $(\mathbb{Z}/n\mathbb{Z}, +)$ 的所有子群的结构、性质和数量。

• 引言: 作者在这里做了一个小结和预告。前面我们为了定义 $\phi(n)$ 暂时偏离了主线，现在回到最初的目标：彻底搞清楚 $\mathbb{Z}/n\mathbb{Z}$ 的所有子群。

• 定理内容逐条解析:

(i) $\mathbb{Z} / n \mathbb{Z}$的每个子群都是循环的。

• 含义: $\mathbb{Z}/n\mathbb{Z}$ 是一个循环群（由 $1$ 生成），这个性质更加强大：它的任何一个子群也必然是循环群。你不可能在 $\mathbb{Z}/n\mathbb{Z}$ 里面找到一个非循环的子群（比如像克莱因四元群那样的）。
• 证明回顾: 在之前的章节中（这里原文说“我们已经看到这一点”），通常的证明思路是：取子群 $H$ 中除 $0$ 以外，“最小的”正元素 $k$。可以证明 $H$ 中所有其他元素都必然是 $k$ 的倍数，因此 $H = \langle k \rangle$。

(ii) 如果 $a \in \mathbb{Z} / n \mathbb{Z}$ 且 $d=\operatorname{gcd}(a, n)$，那么 $\langle a\rangle=\langle d\rangle$。

• 含义: 任何一个元素 $a$ 生成的循环子群，都等于由另一个特殊的元素 $d$ 生成的循环子群，而这个 $d$ 正是 $a$ 与 $n$ 的最大公约数。
• 作用: 这条性质极大地简化了子群的讨论。$\mathbb{Z}/n\mathbb{Z}$ 中有 $n$ 个元素，可能生成各种各样的子群。这条性质说，这些子群的“真实身份”只有那么几个，都等同于由 $n$ 的某个约数 $d$ 所生成的子群。我们只需要研究 $\langle d \rangle$ 这种标准形式的子群就够了。
• 证明思路:
• $\langle a \rangle \subseteq \langle d \rangle$: 因为 $d \mid a$，所以 $a=kd$。在群里就是 $[a] = k \cdot [d]$，所以 $[a]$ 是 $\langle [d] \rangle$ 的一个元素。那么由 $[a]$ 生成的整个子群 $\langle [a] \rangle$ 也必然被包含在 $\langle [d] \rangle$ 中。
• $\langle d \rangle \subseteq \langle a \rangle$: 根据裴蜀定理，$d = xa+yn$。在 $\mathbb{Z}/n\mathbb{Z}$ 中，这意味着 $[d] = [xa+yn] = [xa] + [yn] = x \cdot [a] + y \cdot [n] = x \cdot [a] + [0] = x \cdot [a]$。这说明 $[d]$ 是 $[a]$ 的倍数，所以 $[d] \in \langle [a] \rangle$。因此整个 $\langle [d] \rangle$ 都被包含在 $\langle [a] \rangle$ 中。
• 两者互相包含，所以它们相等。

(iii) 如果 $a \in \mathbb{Z} / n \mathbb{Z}$ 且 $d=\operatorname{gcd}(a, n)$，$a$的阶是 $n/d$。

• 含义: 这给出了计算 $\mathbb{Z}/n\mathbb{Z}$ 中任意元素 $a$ 的阶 (order) 的一个精确公式。元素的阶是指将它与自身相加（因为是加法群）直到第一次得到单位元 $0$ 所需的最小次数。
• 证明思路:
• 根据 (ii)，$\langle a \rangle = \langle d \rangle$。所以 $a$ 的阶等于 $d$ 的阶。
• $d$ 的阶是多少？我们要找最小的正整数 $k$ 使得 $k \cdot d \equiv 0 \pmod n$。
• $kd$ 是 $n$ 的倍数 $\iff kd = mn$ 对某个整数 $m$。
• 两边同除以 $d$，得到 $k = m(n/d)$。
• 我们要找最小的正整数 $k$，那么取 $m=1$ 即可，此时 $k = n/d$。
• 所以 $d$ 的阶是 $n/d$。因此 $a$ 的阶也是 $n/d$。

(iv) $\mathbb{Z} / n \mathbb{Z}$的每个子群的阶整除 $n$。

• 含义: 这是著名的拉格朗日定理在循环群 $\mathbb{Z}/n\mathbb{Z}$ 上的一个具体体现。子群的大小必须能够“整齐地”划分整个群的大小。
• 证明思路: 任何一个子群 $H$ 都是循环的 (i)，所以 $H=\langle a \rangle$。它的阶就是 $a$ 的阶。根据 (iii)，$a$ 的阶是 $n/d$，其中 $d=\operatorname{gcd}(a,n)$。因为 $d$ 是 $n$ 的约数，所以 $n/d$ 也是 $n$ 的一个约数。因此，子群的阶 $n/d$ 必然整除 $n$。

(v) 对于 $n$ 的每个约数 $d$，$\mathbb{Z} / n \mathbb{Z}$ 中恰好有一个阶为 $d$ 的子群，即 $\langle n/d \rangle$。

• 含义: 这条性质揭示了一个惊人的“一一对应”关系。$n$ 有多少个约数，$\mathbb{Z}/n\mathbb{Z}$ 就有多少个不同大小的子群。并且，对于每个可能的阶 $d$（$d$必须是$n$的约数），满足这个阶的子群不仅存在，而且是唯一的。
• 证明思路:
• 存在性: $n$ 的约数 $d$。我们能否构造一个阶为 $d$ 的子群？考虑元素 $a=n/d$。$a$ 也是 $n$ 的一个约数。$\operatorname{gcd}(a, n) = \operatorname{gcd}(n/d, n) = n/d$。根据 (iii)，元素 $a=n/d$ 的阶是 $n / \operatorname{gcd}(a,n) = n / (n/d) = d$。所以子群 $\langle n/d \rangle$ 的阶就是 $d$。存在性得证。
• 唯一性: 假设 $H$ 是任意一个阶为 $d$ 的子群。根据 (i), $H$ 是循环的, $H=\langle a \rangle$。$a$ 的阶是 $d$。根据 (iii), $a$ 的阶 $d = n/\operatorname{gcd}(a,n)$。这意味着 $\operatorname{gcd}(a,n) = n/d$。令 $e = n/d$。我们有 $\operatorname{gcd}(a,n)=e$。根据 (ii)，$\langle a \rangle = \langle \operatorname{gcd}(a,n) \rangle = \langle e \rangle = \langle n/d \rangle$。这说明任何一个阶为 $d$ 的子群，都必然等于 $\langle n/d \rangle$ 这个特定的子群。唯一性得证。

这个推论是定理 1.4.8 的一个直接且极其重要的结果。它完整地刻画了加法群 $(\mathbb{Z}/n\mathbb{Z}, +)$ 的所有生成元。

1. 什么是生成元 (Generator)?
   • 在加法群 $(\mathbb{Z}/n\mathbb{Z}, +)$ 中，一个元素 $a$ 被称为生成元，如果通过重复地将 $a$ 与自身相加，可以得到群中的所有元素。
   • 用符号表示，就是由 $a$ 生成的循环子群 $\langle a \rangle$ 恰好等于整个群 $\mathbb{Z}/n\mathbb{Z}$。
2. 推论的三个等价条件:
   • (1) $\langle a\rangle=\mathbb{Z} / n \mathbb{Z}$: 这是生成元的定义。
   • (2) $\operatorname{gcd}(a, n)=1$: 这是一个数论条件，即 $a$ 与 $n$ 互素。
   • (3) $a \in(\mathbb{Z} / n \mathbb{Z})^{*}$: 这是一个关于乘法群成员资格的条件，即 $a$ 是一个可逆元。
3. 推导过程:
   • 从 (1) 到 (2):
   • $\langle a \rangle = \mathbb{Z}/n\mathbb{Z}$ 意味着由 $a$ 生成的子群的阶是 $n$。
   • 根据定理 1.4.8(iii)，我们知道 $a$ 的阶等于 $n/d$，其中 $d=\operatorname{gcd}(a,n)$。
   • 所以我们有方程 $n/d = n$。
   • 解这个方程，唯一的可能性是 $d=1$。
   • 因此，$\operatorname{gcd}(a,n)=1$。
   • 从 (2) 到 (1):
   • 如果 $\operatorname{gcd}(a,n)=1$，即 $d=1$。
   • 根据定理 1.4.8(iii)，$a$ 的阶是 $n/d = n/1 = n$。
   • 一个阶为 $n$ 的元素，在大小为 $n$ 的群 $\mathbb{Z}/n\mathbb{Z}$ 中，它生成的子群 $\langle a \rangle$ 的大小也是 $n$。
   • 一个大小为 $n$ 的子群，包含在大小为 $n$ 的主群中，那么这个子群必然就是主群本身。
   • 所以 $\langle a \rangle = \mathbb{Z}/n\mathbb{Z}$。
   • 从 (2) 到 (3):
   • $\operatorname{gcd}(a, n)=1$ 是推论 1.4.4 中判断 $a$ 是否为可逆元的充要条件。
   • $(\mathbb{Z} / n \mathbb{Z})^*$ 的定义就是所有可逆元的集合。
   • 所以 $\operatorname{gcd}(a, n)=1 \iff a \in(\mathbb{Z} / n \mathbb{Z})^*$。
4. 结论: 在加法循环群 $(\mathbb{Z}/n\mathbb{Z}, +)$ 中寻找生成元，就等价于在乘法群 $(\mathbb{Z}/n\mathbb{Z})^*$ 中寻找其成员。这两个看似不相关的群，其核心元素集合竟然是同一批！

这段话是对上述易错点的一个非常重要的补充说明，它强调了同一个符号 $a$ 在不同上下文（不同群）中“阶”的含义是完全不同的。

1. 同一个元素，两个身份:
   • 给定一个 $a \in (\mathbb{Z}/n\mathbb{Z})^*$，比如 $a=3, n=10$。
   • 这个元素 $3$ 同时生活在两个世界里：
   • 世界A: 加法群 $(\mathbb{Z}/10\mathbb{Z}, +)$。
   • 世界B: 乘法群 $((\mathbb{Z}/10\mathbb{Z})^*, \cdot)$。
2. 在不同世界中“阶”的含义不同:
   • 在世界A (加法群) 中: $a$ 的阶是最小的正整数 $k$ 使得 $\underbrace{a+a+\dots+a}_{k \text{ 次}} \equiv 0 \pmod n$。
   • 在世界B (乘法群) 中: $a$ 的阶是最小的正整数 $k$ 使得 $a^k \equiv 1 \pmod n$。
3. 计算两个阶:
   • $a$ 作为 $\mathbb{Z}/n\mathbb{Z}$ 元素的阶 (加法阶):
   • 因为 $a \in (\mathbb{Z}/n\mathbb{Z})^*$，所以 $\operatorname{gcd}(a,n)=1$。
   • 根据推论 1.4.9，这意味着 $a$ 是加法群 $(\mathbb{Z}/n\mathbb{Z}, +)$ 的一个生成元。
   • 生成元的阶必然等于群的阶。
   • $(\mathbb{Z}/n\mathbb{Z}, +)$ 的阶是 $n$。
   • 所以，只要 $a$ 是一个可逆元，它在加法群中的阶永远是 $n$。

• $a$ 作为 $(\mathbb{Z}/n\mathbb{Z})^*$ 元素的阶 (乘法阶):
• 这个阶是 $a$ 在乘法下的循环周期。
• 根据拉格朗日定理，这个阶必须整除乘法群 $(\mathbb{Z}/n\mathbb{Z})^*$ 的阶。
• $(\mathbb{Z}/n\mathbb{Z})^*$ 的阶是 $\phi(n)$。
• 所以，$a$ 的乘法阶必然是 $\phi(n)$ 的一个约数。它通常远小于 $n$。

这个推论是将我们刚刚学到的关于加法群 $(\mathbb{Z}/n\mathbb{Z}, +)$ 的所有深刻结论，进行了一次抽象和推广。它告诉我们，那些结论并非 $\mathbb{Z}/n\mathbb{Z}$ 所特有，而是所有有限循环群的普适性质。

1. 抽象化的威力:
   • 在群论中，如果两个群同构 (isomorphic)，那么它们就拥有完全相同的代数结构。所有关于群结构的性质（如子群数量、元素阶的分布等）都可以从一个群平移到另一个群。
   • 任何一个 $n$ 阶有限循环群 $G$，都与加法群 $(\mathbb{Z}/n\mathbb{Z}, +)$ 同构。
   • 这个同构映射可以这样建立：设 $g$ 是 $G$ 的一个生成元，那么可以定义一个映射 $f: \mathbb{Z}/n\mathbb{Z} \to G$ 为 $f([k]_n) = g^k$。可以证明这是一个群同构。
   • 因此，我们在 $\mathbb{Z}/n\mathbb{Z}$ 上证明的所有结构定理，都可以通过这个同构“翻译”成关于 $G$ 的定理。
2. 推论内容逐条“翻译”:
   • 我们来对比定理 1.4.8 和推论 1.4.10。设同构 $f([k])=g^k$。
   • (i) $\mathbb{Z}/n\mathbb{Z}$ 的子群都是循环的 $\implies G$ 的子群也都是循环的。子群的阶整除 $n$ 这个性质也被继承。
   • (ii) 在 $\mathbb{Z}/n\mathbb{Z}$ 中，我们有 $\langle [a] \rangle = \langle [d] \rangle$。在同构映射下，$[a]$ 对应 $g^a$，$[d]$ 对应 $g^d$。所以 $\langle g^a \rangle = \langle g^d \rangle$。
   • 元素 $[a]$ 的阶是 $n/d \implies$ 元素 $g^a$ 的阶也是 $n/d$。
   • $[a]$ 是生成元 $\iff \operatorname{gcd}(a,n)=1 \implies g^a$ 是生成元 $\iff \operatorname{gcd}(a,n)=1$。
   • (iii) $\mathbb{Z}/n\mathbb{Z}$ 中对每个约数 $d$ 有唯一一个阶为 $d$ 的子群 $\langle [n/d] \rangle \implies G$ 中对每个约数 $d$ 也有唯一一个阶为 $d$ 的子群，它就是同构映射下的像 $\langle g^{n/d} \rangle$。
   • (iv) 这是一个新结论，但可以由 (ii) 导出。$G$ 的生成元是形如 $g^a$ 的元素，其条件是 $\operatorname{gcd}(a,n)=1$。那么有多少个这样的 $a$ 呢 (在模 $n$ 的意义下)？$a$ 可以取 $\{1, ..., n-1\}$ 中所有与 $n$ 互素的数。根据欧拉 $\phi$ 函数的定义，这样的 $a$ 正好有 $\phi(n)$ 个。所以 $G$ 的生成元数量是 $\phi(n)$。

这个例子将前面推广的抽象理论（推论 1.4.10）应用到了一个非常具体且重要的数学对象上——复平面上的单位根群。

1. 单位根群 $\mu_n$:
   • 定义: 它是复数域 $\mathbb{C}$ 中所有满足方程 $z^n=1$ 的解的集合。
   • 元素: 根据棣莫弗定理，这些解是 $z_k = e^{2 \pi i k / n} = \cos(2\pi k/n) + i \sin(2\pi k/n)$，其中 $k=0, 1, 2, ..., n-1$。
   • 几何图像: 这些点均匀地分布在复平面的单位圆上，构成一个正 n 边形的顶点。
   • 群结构: $\mu_n$ 在复数乘法下构成一个群。它是一个 $n$ 阶的阿贝尔群。
2. $\mu_n$ 是循环群:
   • 例子明确指出，$\mu_n$ 是一个循环群。
   • 一个显而易见的生成元是 $g = e^{2\pi i / n}$ (即 $k=1$ 时的根)。
   • 为什么？因为它的幂次 $g^k = (e^{2\pi i / n})^k = e^{2\pi i k / n}$，当 $k$ 取 $0, 1, ..., n-1$ 时，正好不重不漏地生成了 $\mu_n$ 的所有元素。
3. 本原单位根 (Primitive Root of Unity):
   • 定义: 一个 $n$ 次单位根 $z$ 被称为本原的，如果它的阶恰好是 $n$。也就是说，$z^n=1$，并且对于任何比 $n$ 小的正整数 $m$，$z^m \ne 1$。
   • 与生成元的关系: 这个定义与“循环群的生成元”的定义是完全一样的。所以，“$z$ 是一个本原 $n$ 次单位根”和“$z$ 是群 $\mu_n$ 的一个生成元”是两个意思完全相同的说法。
4. 寻找所有本原单位根:
   • 我们已经知道了 $\mu_n$ 是一个 $n$ 阶循环群，并且找到了一个生成元 $g = e^{2\pi i / n}$。
   • 现在问题变成：这个群里还有哪些其他的生成元？
   • 我们可以直接套用推论 1.4.10(ii) 的结论：$g^a$ 是生成元 $\iff \operatorname{gcd}(a, n)=1$。
   • 将 $g = e^{2\pi i/n}$ 代入，我们得到：

这个例子是一个综合应用，展示了如何使用前面学到的所有理论来彻底分析一个具体的乘法群——$(\mathbb{Z} / 7 \mathbb{Z})^*$。

第一部分：证明群是循环的并找到生成元

1. 群的基本信息:
   • 群: $(\mathbb{Z} / 7 \mathbb{Z})^*$，运算是模 7 乘法。
   • 元素: $7$ 是素数，所以元素是 $\{1, 2, 3, 4, 5, 6\}$。
   • 阶: 群的阶是 $\phi(7) = 7-1=6$。
2. 寻找生成元 (试错法):
   • 一个群是循环群，当且仅当它有一个阶等于群的阶的元素。我们要找一个 6 阶元素。
   • 尝试元素 2:
   • $2^1=2$
   • $2^2=4$
   • $2^3=8 \equiv 1 \pmod 7$。
   • 计算到此停止。$2$ 的阶是 $3$。因为 $3 < 6$，所以 $2$ 不是生成元。
   • 尝试元素 3:
   • $3^1=3$
   • $3^2=9 \equiv 2 \pmod 7$
   • $3^3=3 \cdot 3^2 \equiv 3 \cdot 2 = 6 \equiv -1 \pmod 7$。
   • 这是一个有用的中间结果。如果 $3^3=-1$，那么 $(3^3)^2 = (-1)^2 = 1$，即 $3^6=1$。
   • 根据拉格朗日定理，$3$ 的阶必须整除群的阶 $6$。所以 $3$ 的阶可能是 $1, 2, 3, 6$。
   • 我们已经算到 $3^1, 3^2, 3^3$ 都不等于 $1$，所以阶不是 $1, 2, 3$。
   • 因此，$3$ 的阶必然是 $6$。
   • 结论: 我们找到了一个阶为 $6$ 的元素 $3$。因此，$(\mathbb{Z} / 7 \mathbb{Z})^*$ 是一个 6 阶循环群，且 $3$ 是它的一个生成元。记作 $(\mathbb{Z} / 7 \mathbb{Z})^* = \langle 3 \rangle$。

第二部分：应用循环群理论分析其结构

• 既然我们已经确定 $(\mathbb{Z} / 7 \mathbb{Z})^*$ 是一个 6 阶循环群，我们就可以应用推论 1.4.10 的所有结论了。

1. 子群结构:
   • 群的阶 $n=6$。$6$ 的约数有 $1, 2, 3, 6$。
   • 根据推论 1.4.10(iii)，对于每个约数 $d$，都恰好有唯一一个阶为 $d$ 的子群。
   • 这个唯一的子群由 $\langle g^{n/d} \rangle$ 生成，这里 $g=3, n=6$。
   • 阶为 1 的子群: $d=1$。子群是 $\langle 3^{6/1} \rangle = \langle 3^6 \rangle = \langle 1 \rangle = \{1\}$。
   • 阶为 2 的子群: $d=2$。子群是 $\langle 3^{6/2} \rangle = \langle 3^3 \rangle = \langle 6 \rangle = \{1, 6\}$。
   • 阶为 3 的子群: $d=3$。子群是 $\langle 3^{6/3} \rangle = \langle 3^2 \rangle = \langle 2 \rangle = \{1, 2, 4\}$。 (因为 $2^1=2, 2^2=4, 2^3=1$)
   • 阶为 6 的子群: $d=6$。子群是 $\langle 3^{6/6} \rangle = \langle 3^1 \rangle = \langle 3 \rangle$，即群自身。
2. 生成元:
   • 根据推论 1.4.10(iv)，生成元的数量是 $\phi(n) = \phi(6) = 2$。
   • 根据推论 1.4.10(ii)，生成元是形如 $g^a = 3^a$ 的元素，其中 $\operatorname{gcd}(a, n) = \operatorname{gcd}(a, 6) = 1$。
   • 在 $1 \le a < 6$ 中，满足条件的 $a$ 是 $1$ 和 $5$。
   • 所以两个生成元是：
   • $a=1: 3^1 = 3$。
   • $a=5: 3^5 = 3^{-1}$ (在 6 阶群中，$a=5$ 和 $a=-1$ 等价)。要计算 $3^{-1} \pmod 7$，就是解方程 $3x \equiv 1 \pmod 7$。我们发现 $3 \cdot 5 = 15 \equiv 1 \pmod 7$。所以 $3^5=5$。
   • 因此，两个生成元是 $3$ 和 $5$。

这个推论回答了一个非常精确的计数问题：在加法群 $(\mathbb{Z}/n\mathbb{Z}, +)$ 中，具有特定阶的元素到底有多少个？

1. 问题: 给定一个整数 $n$，再给定一个 $n$ 的约数 $d$。在群 $\mathbb{Z}/n\mathbb{Z}$ 中，有多少个元素的加法阶恰好是 $d$？
   • 注意：如果 $d$ 不是 $n$ 的约数，根据拉格朗日定理的推论（对于循环群，元素阶必须整除群阶），阶为 $d$ 的元素数量是 0。所以我们只关心 $d$ 是 $n$ 的约数的情况。
2. 结论: 数量恰好是 $\phi(d)$。这里的 $\phi$ 是欧拉函数。
3. 证明思路的剖析:
   • 第一步：找到容身之所。一个阶为 $d$ 的元素 $a$，它生成的子群 $\langle a \rangle$ 的阶也必须是 $d$。
   • 第二步：找到唯一的“家”。根据定理 1.4.8(v)，$\mathbb{Z}/n\mathbb{Z}$ 中阶为 $d$ 的子群是唯一的，这个子群就是 $H = \langle n/d \rangle$。
   • 第三步：元素的身份。因此，任何一个阶为 $d$ 的元素 $a$，它生成的子群 $\langle a \rangle$ 必须等于这个唯一的 $d$ 阶子群 $H$。这意味着，$a$ 必须是 $H$ 的一个生成元！
   • 如果 $a \in H$ 但不是生成元，那么 $a$ 的阶将是 $d$ 的一个真约数，与假设矛盾。
   • 如果 $a \notin H$，那么 $\langle a \rangle$ 就不是 $H$，也与 $H$ 的唯一性矛盾。
   • 第四步：计数生成元。现在问题转化为：子群 $H = \langle n/d \rangle$ 有多少个生成元？
   • $H$ 本身是一个循环群，它的阶是 $d$。
   • 根据推论 1.4.10(iv)，一个 $d$ 阶循环群，其生成元的数量是 $\phi(d)$。
   • 最终结论: $\mathbb{Z}/n\mathbb{Z}$ 中阶为 $d$ 的元素的数量，就等于这个唯一的 $d$ 阶子群的生成元的数量，即 $\phi(d)$。

这个备注在前一个推论的基础上，给出了那些特定阶元素具体长什么样的一个明确“公式”。

1. 背景: 推论 1.4.13 告诉我们阶为 $d$ 的元素有 $\phi(d)$ 个，但没说它们具体是谁。这个备注填补了这一空白。
2. 核心论点: $\mathbb{Z}/n\mathbb{Z}$ 中所有阶为 $d$ 的元素的集合，就是下面这个集合：

注意，这里的运算都是在 $\mathbb{Z}/n\mathbb{Z}$ 中进行的，所以是 $[k \cdot (n/d)]_n$。

1. 公式的理解:
   • $n/d$: 这是什么？根据定理 1.4.8(v)，唯一的 $d$ 阶子群是由元素 $g = n/d$ 生成的。所以 $g$ 是这个 $d$ 阶子群的一个生成元。
   • $k \cdot (n/d)$: 这表示取这个生成元 $g=n/d$ 的 $k$ 倍。
   • $\operatorname{gcd}(k, d)=1$: 这是什么条件？在一个 $d$ 阶循环群 $\langle g \rangle$ 中，根据推论 1.4.10(ii)，元素 $g^k$ (在加法群中是 $k \cdot g$) 是生成元的充要条件是 $\operatorname{gcd}(k, d)=1$。
   • 结合起来: 整个集合的描述就是：“取那个唯一的 $d$ 阶子群 $\langle n/d \rangle$，然后找出它所有的生成元”。这和推论 1.4.13 的证明逻辑是完全一致的。

这个推论是数论中一个非常著名和优美的恒等式，有时被称为高斯恒等式。它揭示了欧拉 $\phi$ 函数自身的一个深刻的内在规律。

1. 恒等式解析:
   • $\sum_{d \mid n}$: 这个符号表示对所有 $n$ 的正约数 $d$ 进行求和。
   • $\phi(d)$: 对每个约数 $d$，我们计算它的欧拉 $\phi$ 函数值。
   • $= n$: 将所有这些 $\phi(d)$ 的值加起来，其总和恰好等于 $n$ 本身。
2. 证明思路 (基于群论):
   • 这个证明是一个非常精彩的“分类计数”的例子，也被称为“谢菲尔德大学方法”(Shepherd's principle)。
   • 第一步：划分总体。考虑加法群 $\mathbb{Z}/n\mathbb{Z}$，它有 $n$ 个元素。我们将这 $n$ 个元素按照它们的阶 (order) 来进行分类。
   • 第二步：确定可能类别。根据拉格朗日定理在循环群中的加强版（定理 1.4.8），$\mathbb{Z}/n\mathbb{Z}$ 中任何一个元素的阶都必须是 $n$ 的一个约数。所以，所有可能的“阶”的类别就是 $n$ 的所有约数 $d$。
   • 第三步：计算每个类别的数量。对于每个可能的阶 $d$ (其中 $d \mid n$)，阶为 $d$ 的元素有多少个？推论 1.4.13 完美地回答了这个问题：数量恰好是 $\phi(d)$。
   • 第四步：加总所有类别。我们将所有类别的元素数量加起来，就应该得到总的元素数量。
   • （阶为 $d_1$ 的元素数量）+（阶为 $d_2$ 的元素数量）+ ...
   • 这正是 $\phi(d_1) + \phi(d_2) + ...$
   • 用求和符号表示，就是 $\sum_{d \mid n} \phi(d)$。
   • 第五步：得出结论。因为我们对群 $\mathbb{Z}/n\mathbb{Z}$ 的所有 $n$ 个元素进行了不重不漏的分类计数，所以所有类别数量之和必然等于总元素数 $n$。
   • 因此，$\sum_{d \mid n} \phi(d) = n$。

这个备注是一个非常重要的“概念辨析”和“视野拓展”。它将我们目前学到的循环群的优美性质，与更广阔的一般有限群世界进行对比，突显出循环群的特殊性。

1. 共性：拉格朗日定理 (Lagrange's Theorem)
   • 我们从定理 1.4.8(iv) 中得知，循环群的子群的阶必然整除主群的阶。
   • 备注指出，这实际上是一个更普适的定理——拉格朗日定理——的特例。
   • 拉格朗日定理说：对于任何一个有限群 $G$ (不一定是循环群，也不一定是阿贝尔群)，只要 $H$ 是它的一个子群，那么 $H$ 的大小 $\#(H)$ 必须整除 $G$ 的大小 $\#(G)$。
   • 这是一个单向的结论：“有子群 $\implies$ 阶整除”。
2. 差异：拉格朗日定理的逆命题
   • 逆命题: 如果 $d$ 是群 $G$ 的阶 $\#(G)$ 的一个约数，那么 $G$ 是否一定存在一个阶为 $d$ 的子群？
   • 对于循环群: 答案是肯定的。定理 1.4.8(v) 告诉我们，对于每个约数 $d$，不仅存在，而且恰好只有一个阶为 $d$ 的子群。这是循环群一个极强的、非常优美的性质。
   • 对于一般有限群: 答案是否定的！拉格朗日定理的逆命题在一般情况下不成立。这是有限群论中一个非常深刻和重要的事实。
3. 反例:
   • 备注给出了一些例子来说明一般有限群的复杂性。
   • 可能没有阶为 $d$ 的子群: 最小的反例是 12 阶的交错群 $A_4$ (正四面体旋转群)。$A_4$ 的阶是 12，6 是 12 的一个约数，但是 $A_4$ 中没有任何阶为 6 的子群。
   • 可能有多个阶为 $d$ 的子群:
   • 克莱因四元群 $V_4 \cong (\mathbb{Z}/2\mathbb{Z}) \times (\mathbb{Z}/2\mathbb{Z})$: 阶是 4。2 是 4 的约数。这个群有 3 个 不同的阶为 2 的子群。
   • 二面体群 $D_3$ (或对称群 $S_3$): 阶是 6。2 是 6 的约数。它有 3 个 阶为 2 的子群（由三个对换生成）。3 是 6 的约数，它有 1 个 阶为 3 的子群（由旋转生成）。
   • 四元数群 $Q_8$: 阶是 8。4 是 8 的约数。它有 3 个 不同的阶为 4 的子群（由 $\langle i \rangle, \langle j \rangle, \langle k \rangle$ 生成）。

这个定理是数论和群论中一个里程碑式的结论，它揭示了在特定条件下，两个较小的循环群的直积可以“合并”成一个更大的循环群。

1. 定理的条件:
   • $n, m$ 是两个正整数。
   • 核心条件：$\operatorname{gcd}(n, m)=1$，即 $n$ 和 $m$ 互素。这是定理成立的关键。
2. 定理的结论 (群论形式):
   • 直积群 $(\mathbb{Z}/n\mathbb{Z}) \times (\mathbb{Z}/m\mathbb{Z})$ 与循环群 $\mathbb{Z}/nm\mathbb{Z}$ 是同构的。
   • 什么是直积群？: $(\mathbb{Z}/n\mathbb{Z}) \times (\mathbb{Z}/m\mathbb{Z})$ 是一个由有序对 $(a, b)$ 组成的群，其中 $a \in \mathbb{Z}/n\mathbb{Z}$，$b \in \mathbb{Z}/m\mathbb{Z}$。群的运算是“按分量进行”的，即 $(a_1, b_1) + (a_2, b_2) = (a_1+a_2, b_1+b_2)$。这个群的阶是 $n \times m$。
   • 同构的含义: 这两个群 $(\mathbb{Z}/n\mathbb{Z}) \times (\mathbb{Z}/m\mathbb{Z})$ 和 $\mathbb{Z}/nm\mathbb{Z}$ 在代数结构上是完全一样的。可以找到一个一一对应的映射，这个映射保持了群的运算。这意味着，研究那个看起来更复杂的直积群，就等同于研究那个我们非常熟悉的、结构更简单的循环群 $\mathbb{Z}/nm\mathbb{Z}$。
3. 等价表述:
   • 定理的另一个等价说法是：直积群 $(\mathbb{Z}/n\mathbb{Z}) \times (\mathbb{Z}/m\mathbb{Z})$ 是一个循环群。
   • 为什么等价？
   • 一个有限群是循环群，当且仅当它同构于 $\mathbb{Z}/k\mathbb{Z}$，其中 $k$ 是该群的阶。
   • 直积群 $(\mathbb{Z}/n\mathbb{Z}) \times (\mathbb{Z}/m\mathbb{Z})$ 的阶是 $nm$。
   • 所以，说它同构于 $\mathbb{Z}/nm\mathbb{Z}$，就完全等价于说它是一个阶为 $nm$ 的循环群。
4. 直观意义:
   • 当 $n, m$ 互素时，两个独立的“周期性”系统（一个周期为 $n$，一个周期为 $m$）组合在一起，会产生一个更大的、统一的周期性系统，其周期是 $n \times m$。
   • 例如，一个周期为 3 的事件和一个周期为 5 的事件，它们同时发生的周期将是 $3 \times 5 = 15$。

这是中国剩余定理更古老、更广为人知的数论形式。它直接描述了一个关于解同余方程组的问题。

1. 定理的组成: 这个定理包含两个部分：解的存在性和解的唯一性（在模 $nm$ 意义下）。
2. 存在性部分:
   • 条件: 模数 $n, m$ 必须互素。
   • 输入: 任意给定两个整数 $r$ 和 $s$。
   • 结论: 总能找到至少一个整数 $x$，这个 $x$ 非常特殊，它同时满足两个条件：
   • $x$ 除以 $n$ 的余数是 $r$。
   • $x$ 除以 $m$ 的余数是 $s$。
   • 换句话说: 无论你对余数提出什么样的要求（只要模数互素），总有一个数能满足你的所有要求。
3. 唯一性部分:
   • 结论: 如果你找到了一个解 $x$，那么所有其他的解 $x'$ 都和 $x$ 有一个非常简单的关系：$x' \equiv x \pmod{nm}$。
   • 换句话G说: 所有的解构成一个同余类，模数是 $nm$。在模 $nm$ 的意义下，解是唯一的。如果你找到了一个解 $x_0$，那么所有的解就是 $\{..., x_0-nm, x_0, x_0+nm, x_0+2nm, ...\}$。
4. 与群论形式的联系:
   • 群论形式说 $(\mathbb{Z}/n\mathbb{Z}) \times (\mathbb{Z}/m\mathbb{Z}) \cong \mathbb{Z}/nm\mathbb{Z}$。这个同构映射 $f$ 通常就是 $f([x]_{nm}) = ([x]_n, [x]_m)$。
   • 同构意味着这个映射是双射（一一对应）。
   • 满射 (Surjective) 部分：对于目标群 $(\mathbb{Z}/n\mathbb{Z}) \times (\mathbb{Z}/m\mathbb{Z})$ 中的任何一个元素 $([r]_n, [s]_m)$，都存在一个源群 $\mathbb{Z}/nm\mathbb{Z}$ 中的元素 $[x]_{nm}$ 映射到它。即 $f([x]_{nm}) = ([x]_n, [x]_m) = ([r]_n, [s]_m)$。这恰恰就是说，存在一个 $x$，使得 $x \equiv r \pmod n$ 且 $x \equiv s \pmod m$。这就是数论形式的存在性。
   • 单射 (Injective) 部分：如果 $f([x]_{nm}) = f([x']_{nm})$，那么必须有 $[x]_{nm} = [x']_{nm}$。也就是说，如果 $x, x'$ 都映射到同一个 $([r]_n, [s]_m)$，那么 $x$ 和 $x'$ 必须在模 $nm$ 的意义下是同一个同余类。这恰恰就是数论形式的唯一性。
   • 因此，群论形式是数论形式的一个更抽象、更简洁的代数封装。

这个引理给出了计算直积群中一个元素阶的通用公式。这是证明中国剩余定理群论形式的关键一步。

1. 引理的设定:
   • 我们有两个群 $G_1, G_2$ (不要求是循环群或阿贝尔群)。
   • 我们从每个群中各取一个元素 $g_1, g_2$。
   • 我们知道这两个元素各自的阶：$g_1$ 的阶是 $d_1$, $g_2$ 的阶是 $d_2$。
   • 我们构造一个直积群 $G_1 \times G_2$，并考虑其中的一个组合元素 $(g_1, g_2)$。
2. 问题: 直积群中的元素 $(g_1, g_2)$ 的阶是多少？
   • 元素的阶的定义是：最小的正整数 $k$ 使得 $(g_1, g_2)^k$ 等于直积群的单位元 $(e_1, e_2)$，其中 $e_1, e_2$ 分别是 $G_1, G_2$ 的单位元。
   • 直积群的运算是按分量进行的，所以 $(g_1, g_2)^k = (g_1^k, g_2^k)$。
   • 所以问题转化为：找到最小的正整数 $k$ 使得 $g_1^k = e_1$ 并且 $g_2^k = e_2$。
3. 结论: 这个最小的正整数 $k$ 正是 $d_1$ 和 $d_2$ 的最小公倍数 (least common multiple, lcm)。
4. 证明思路 (练习):
   • 设 $k$ 是 $(g_1, g_2)$ 的阶。
   • 条件 $g_1^k = e_1$ 意味着 $k$ 必须是 $g_1$ 的阶 $d_1$ 的一个倍数 (因为 $d_1$ 是满足此条件的最小正整数)。所以 $k = a \cdot d_1$。
   • 条件 $g_2^k = e_2$ 意味着 $k$ 必须是 $g_2$ 的阶 $d_2$ 的一个倍数。所以 $k = b \cdot d_2$。
   • 因此，$k$ 必须既是 $d_1$ 的倍数，也是 $d_2$ 的倍数。即，$k$ 是 $d_1$ 和 $d_2$ 的一个公倍数。
   • 因为我们找的是最小的正整数 $k$，所以 $k$ 必须是 $d_1$ 和 $d_2$ 的最小公倍数。
   • 记作 $k = \operatorname{lcm}(d_1, d_2)$。

这一段给出了中国剩余定理 (定理 1.5.1) 的一个简洁而优雅的证明。

1. 证明的目标:
   • 我们要证明，当 $\operatorname{gcd}(n,m)=1$ 时，直积群 $G = (\mathbb{Z}/n\mathbb{Z}) \times (\mathbb{Z}/m\mathbb{Z})$ 是一个阶为 $nm$ 的循环群。
   • 要证明一个有限群是循环群，最直接的方法就是在群里找到一个生成元，即找到一个阶等于群的阶的元素。
   • $G$ 的阶是 $n \times m$。所以，我们的目标是：在 $G$ 中找到一个阶为 $nm$ 的元素。
2. 选择候选元素:
   • 最自然、最简单的候选元素就是 $([1]_n, [1]_m)$，简写为 $(1,1)$。
3. 计算候选元素的阶:
   • 我们使用刚刚学过的引理 1.5.3。
   • 在群 $\mathbb{Z}/n\mathbb{Z}$ 中，元素 $1$ 是生成元，它的阶是 $d_1=n$。
   • 在群 $\mathbb{Z}/m\mathbb{Z}$ 中，元素 $1$ 是生成元，它的阶是 $d_2=m$。
   • 根据引理，直积群中的元素 $(1,1)$ 的阶是 $\operatorname{lcm}(d_1, d_2) = \operatorname{lcm}(n, m)$。
4. 使用数论公式:
   • 有一个基本的数论公式：对于任意两个正整数 $n, m$，它们的最大公约数和最小公倍数满足关系 $\operatorname{lcm}(n,m) \cdot \operatorname{gcd}(n,m) = n \cdot m$。
   • 因此，$\operatorname{lcm}(n,m) = \frac{nm}{\operatorname{gcd}(n,m)}$。
5. 应用定理的核心条件:
   • 本定理的核心条件是 $\operatorname{gcd}(n,m)=1$。
   • 将这个条件代入上面的公式，我们得到 $\operatorname{lcm}(n,m) = \frac{nm}{1} = nm$。
6. 得出结论:
   • 我们已经算出了元素 $(1,1)$ 的阶是 $nm$。
   • 这个阶 $nm$ 正好等于整个直积群 $(\mathbb{Z}/n\mathbb{Z}) \times (\mathbb{Z}/m\mathbb{Z})$ 的阶。
   • 在一个有限群中，如果一个元素的阶等于群的阶，那么这个元素就是一个生成元，并且这个群是一个循环群。
   • 因此，$(\mathbb{Z}/n\mathbb{Z}) \times (\mathbb{Z}/m\mathbb{Z})$ 是一个由 $(1,1)$ 生成的、阶为 $nm$ 的循环群。
   • 根据循环群的同构理论，任何阶为 $k$ 的循环群都同构于 $\mathbb{Z}/k\mathbb{Z}$。
   • 所以，$(\mathbb{Z}/n\mathbb{Z}) \times (\mathbb{Z}/m\mathbb{Z}) \cong \mathbb{Z}/nm\mathbb{Z}$。
   • 证明完毕。

这个备注探讨了当中国剩余定理的核心条件不满足时会发生什么，即当 $\operatorname{gcd}(n,m)>1$ 时。

1. 引理的普适性:
   • 备注首先指出，用于计算直积群元素阶的引理 1.5.3 是普遍适用的，它不要求 $n, m$ 互素。
   • 即，对于任何直积群 $(\mathbb{Z}/n\mathbb{Z}) \times (\mathbb{Z}/m\mathbb{Z})$ 中的任意元素 $(a,b)$，其阶总是 $\operatorname{lcm}(\text{ord}(a), \text{ord}(b))$。
2. 元素阶的上限:
   • 考虑任意一个元素 $(a,b) \in (\mathbb{Z}/n\mathbb{Z}) \times (\mathbb{Z}/m\mathbb{Z})$。
   • $a$ 的阶 $\operatorname{ord}(a)$ 必然整除 $n$。
   • $b$ 的阶 $\operatorname{ord}(b)$ 必然整除 $m$。
   • 因此，$(a,b)$ 的阶 $\operatorname{lcm}(\operatorname{ord}(a), \operatorname{ord}(b))$ 必然整除 $\operatorname{lcm}(n,m)$。
   • 这意味着，群里所有元素的阶，最大也不可能超过 $\operatorname{lcm}(n,m)$。这个 $\operatorname{lcm}(n,m)$ 成为了群中元素阶的一个“天花板”。
3. 当 $\operatorname{gcd}(n,m) > 1$ 时的关键后果:
   • 我们使用数论公式 $\operatorname{lcm}(n,m) = \frac{nm}{\operatorname{gcd}(n,m)}$。
   • 如果 $\operatorname{gcd}(n,m) > 1$，那么分母就大于 1，导致 $\operatorname{lcm}(n,m) < nm$。
   • 这个“天花板”的高度严格小于整个群的阶 $nm$。
4. 最终结论:
   • 既然群里所有元素的阶都小于等于 $\operatorname{lcm}(n,m)$，而 $\operatorname{lcm}(n,m)$ 又严格小于群的阶 $nm$，那么这个群里就绝对不可能存在一个阶为 $nm$ 的元素。
   • 没有阶等于群阶的元素，就意味着这个群没有生成元。
   • 因此，当 $\operatorname{gcd}(n,m)>1$ 时，直积群 $(\mathbb{Z}/n\mathbb{Z}) \times (\mathbb{Z}/m\mathbb{Z})$ 永远不是循环群。
5. 例子:
   • 以 $(\mathbb{Z}/2\mathbb{Z}) \times (\mathbb{Z}/2\mathbb{Z})$ 为例。$n=2, m=2, \operatorname{gcd}(2,2)=2>1$。
   • 群的阶是 4。
   • 元素阶的“天花板”是 $\operatorname{lcm}(2,2) = 2$。
   • 这意味着群里所有非单位元元素的阶最大就是 2。
   • 这与我们之前手动计算的结果（所有非单位元元素的阶都是 2）完全吻合。因为没有 4 阶元素，所以它不是循环群。

这一段详细阐述了为什么群论形式的中国剩余定理（定理 1.5.1）与数论形式的中国剩余定理（定理 1.5.2）是等价的。其核心在于理解群同构的深刻含义。

1. 构造同构映射 $f$:
   • 我们已经证明了，当 $\operatorname{gcd}(n,m)=1$ 时，$\mathbb{Z}/nm\mathbb{Z}$ 和 $(\mathbb{Z}/n\mathbb{Z}) \times (\mathbb{Z}/m\mathbb{Z})$ 都是阶为 $nm$ 的循环群，因此它们必然同构。
   • 现在我们给出一个具体的同构映射 $f$。
   • 映射的定义是：$f([a]_{nm}) = ([a]_n, [a]_m)$。
   • 这个映射的直观意思是：把一个“大钟表”（模 $nm$）上的时间 $a$，同时投影到两个“小钟表”（模 $n$ 和模 $m$）上，看看分别显示几点。
2. 映射的良定义性:
   • 括号里的内容解释了为什么这个映射 $f$ 是良定义的。
   • 一个函数 $f([a]_{nm}) = ...$ 是良定义的，意味着如果 $[a]_{nm} = [b]_{nm}$，那么 $f([a]_{nm})$ 必须等于 $f([b]_{nm})$。
   • $f$ 实际上是由两个分量函数 $g_1([a]_{nm}) = [a]_n$ 和 $g_2([a]_{nm}) = [a]_m$ 组成的。
   • 我们来看 $g_1$。如果 $[a]_{nm} = [b]_{nm}$，则 $a \equiv b \pmod{nm}$，即 $a-b$ 是 $nm$ 的倍数。因为 $n$ 整除 $nm$，所以 $a-b$ 也必然是 $n$ 的倍数，即 $a \equiv b \pmod n$。这就意味着 $[a]_n = [b]_n$。所以 $g_1$ 是良定义的。同理 $g_2$ 也是良定义的。因此 $f$ 是良定义的。
3. $f$ 是同构:
   • 要证明 $f$ 是同构，需要证明它是群同态且是双射。
   • 同态: $f([a]_{nm} + [b]_{nm}) = f([a+b]_{nm}) = ([a+b]_n, [a+b]_m) = ([a]_n+[b]_n, [a]_m+[b]_m) = ([a]_n, [a]_m) + ([b]_n, [b]_m) = f([a]_{nm}) + f([b]_{nm})$。保持了加法运算。
   • 双射: 因为两个群都是有限群且阶相同 ($nm$)，根据抽象代数理论，一个从有限群到同阶有限群的同态，如果它是单射或满射之一，就必然是双射。我们的证明（1.4.4节）实际上是通过证明源群的生成元 $[1]_{nm}$ 的像 $([1]_n, [1]_m)$ 是目标群的生成元来证明满射性，从而证明了同构。
4. 同构与数论形式的联系:
   • 既然 $f$ 是一个双射（一一对应），那么：
   • 满射 (Surjective) 性: 对于目标集 $(\mathbb{Z}/n\mathbb{Z}) \times (\mathbb{Z}/m\mathbb{Z})$ 中的任何一个元素，比如 $([r]_n, [s]_m)$，都必然存在一个源集 $\mathbb{Z}/nm\mathbb{Z}$ 中的元素 $[x]_{nm}$ 被 $f$ 映射到它。
   • 写出来就是：$\exists [x]_{nm}, \text{ s.t. } f([x]_{nm}) = ([x]_n, [x]_m) = ([r]_n, [s]_m)$。
   • 这等价于方程组 $x \equiv r \pmod n$ 和 $x \equiv s \pmod m$ 有解。这就是数论形式的存在性！
   • 单射 (Injective) 性: 如果两个不同的元素 $[x]_{nm}$ 和 $[x']_{nm}$，它们不能被映射到同一个像。即，如果 $f([x]_{nm}) = f([x']_{nm})$，那么必然有 $[x]_{nm} = [x']_{nm}$。
   • 写出来就是：如果 $x$ 和 $x'$ 都是方程组的解，那么 $([x]_n, [x]_m) = ([x']_n, [x']_m)$，这必然导致 $[x]_{nm} = [x']_{nm}$。
   • 这等价于说，解在模 $nm$ 的意义下是唯一的。这就是数论形式的唯一性！

这个备注对中国剩余定理做了一些补充说明和延伸。

(1) 显式推导方法:

• 我们之前的证明（无论是群论的还是从同构推导的）都属于“存在性证明”。它们雄辩地证明了解一定存在，但没有告诉我们具体如何找到这个解 $x$。
• 备注指出，存在另外一种更古老的、构造性的证明方法。这种方法会一步步地教你如何计算出 $x$。
• 典型构造方法 (以两个模数为例):

1. 解方程 $ax+by=1$ (用扩展欧几里得算法)，其中 $a=m, b=n$。得到一组解 $(x_0, y_0)$ 使得 $mx_0+ny_0=1$。
2. 令 $e_1 = ny_0$ 和 $e_2 = mx_0$。我们有 $e_1 \equiv 1 \pmod m, e_1 \equiv 0 \pmod n$ 以及 $e_2 \equiv 1 \pmod n, e_2 \equiv 0 \pmod m$。
3. 那么方程组 $x \equiv r \pmod n, x \equiv s \pmod m$ 的一个解就是 $x = r \cdot e_2 + s \cdot e_1$。
   • 这个构造过程本身就是对定理的另一种证明。

(2) 模数不互素的情况:

• 中国剩余定理要求模数互素。如果不互素会怎样？解还存在吗？
• 备注指出，在这种情况下，我们也可以给出一个明确的判别准则。
• 推导准则:
• $x \equiv r \pmod n \implies x = kn+r$。
• 代入第二个方程: $kn+r \equiv s \pmod m$。
• $kn \equiv s-r \pmod m$。
• 这是一个形如 $Ax=C$ 的线性同余方程，其中未知数是 $k$，$A=n, C=s-r$，模数是 $m$。
• 根据我们之前学的命题 1.4.3，这个关于 $k$ 的方程有解的充分必要条件是 $\operatorname{gcd}(A, m) \mid C$。
• 即 $\operatorname{gcd}(n, m) \mid (s-r)$。
• 结论: 当 $n,m$ 不互素时，同余方程组有解的充要条件是 $r \equiv s \pmod{\operatorname{gcd}(n,m)}$。也就是说，两个余数 $r,s$ 本身必须在模 $\operatorname{gcd}(n,m)$ 的意义下是同余的。如果解存在，那么解在模 $\operatorname{lcm}(n,m)$ 的意义下是唯一的。

这个命题将中国剩余定理从加法群的世界，“升级”到了乘法群的世界。它回答了问题：大的乘法群 $(\mathbb{Z}/nm\mathbb{Z})^*$ 和小的乘法群 $(\mathbb{Z}/n\mathbb{Z})^*, (\mathbb{Z}/m\mathbb{Z})^*$ 之间有什么关系？

1. 命题的设置:
   • 前提: 仍然是 $\operatorname{gcd}(n,m)=1$。
   • 基础: 我们已经有了加法群之间的同构 $f: \mathbb{Z}/nm\mathbb{Z} \to (\mathbb{Z}/n\mathbb{Z}) \times (\mathbb{Z}/m\mathbb{Z})$，定义为 $f(a)=(a,a)$。
   • 操作: 我们现在只关心可逆元。我们把函数 $f$ 的定义域，从整个 $\mathbb{Z}/nm\mathbb{Z}$，限制 (restrict) 到它的子集——乘法群 $(\mathbb{Z}/nm\mathbb{Z})^*$ 上。这个被限制后的新函数，我们叫它 $g$。
   • 所以 $g$ 的作用仍然是 $g(a)=(a,a)$，但它只接受那些与 $nm$ 互素的 $a$ 作为输入。
2. 结论 (i): $g$ 的像 (Image)
   • 像的定义: 函数 $g$ 的所有可能的输出值构成的集合。
   • 结论: $g$ 的像恰好是直积乘法群 $(\mathbb{Z}/n\mathbb{Z})^* \times (\mathbb{Z}/m\mathbb{Z})^*$。
   • 这意味着什么？
   • 首先 (像 $\subseteq \dots$): 如果你输入一个与 $nm$ 互素的 $a$，那么输出的两个分量 $([a]_n, [a]_m)$ 也必然是各自乘法群的成员。即 $[a]_n$ 与 $n$ 互素，$[a]_m$ 与 $m$ 互素。这基于一个数论事实：$\operatorname{gcd}(a, nm)=1 \iff \operatorname{gcd}(a,n)=1 \text{ and } \operatorname{gcd}(a,m)=1$。
   • 其次 (像 $\supseteq \dots$): 对于目标乘法群中的任何一个元素对 $(r,s)$ (其中 $r$ 与 $n$ 互素, $s$ 与 $m$ 互素)，你总能找到源乘法群 $(\mathbb{Z}/nm\mathbb{Z})^*$ 中的一个元素 $a$，使得 $g(a)=(r,s)$。这部分依赖于 $f$ 的满射性。
3. 结论 (ii): $f^*$ 是同构
   • $f^*$ 的定义: 既然我们已经知道 $g$ 建立了一个从 $(\mathbb{Z}/nm\mathbb{Z})^*$ 到 $(\mathbb{Z}/n\mathbb{Z})^* \times (\mathbb{Z}/m\mathbb{Z})^*$ 的双射 (因为 $f$ 是单射，而 $g$ 的像又是整个目标集，所以 $g$ 是双射)，我们就给这个双射起个新名字 $f^*$。
   • 同构结论: 这个双射 $f^*$ 不仅仅是一个集合上的一一对应，它还是一个群同构。这意味着它保持了乘法运算。
   • 即 $f^*(ab) = f^*(a) f^*(b)$。
   • 证明:
   • $f^*(ab) = f(ab) = (ab \pmod n, ab \pmod m)$。
   • $f^*(a)f^*(b) = (a \pmod n, a \pmod m) \cdot (b \pmod n, b \pmod m)$
   • 两者相等，同构成立。
   • 最终公式: 这个同构关系可以简洁地写为 $(\mathbb{Z}/nm\mathbb{Z})^* \cong (\mathbb{Z}/n\mathbb{Z})^* \times (\mathbb{Z}/m\mathbb{Z})^*$。

这个推论是前一个命题的直接、自然的产物，也是欧拉 $\phi$ 函数最重要的性质之一：积性 (multiplicativity)。

1. 积性函数的定义: 在数论中，一个函数 $f: \mathbb{N} \to \mathbb{C}$ 被称为积性函数，如果对于任何一对互素的正整数 $n,m$，总是有 $f(nm) = f(n)f(m)$。
2. 推导过程:
   • 我们从命题 1.5.6 的同构关系出发：$(\mathbb{Z}/nm\mathbb{Z})^* \cong (\mathbb{Z}/n\mathbb{Z})^* \times (\mathbb{Z}/m\mathbb{Z})^*$。
   • 群同构意味着两个群的阶（元素个数）是相等的。
   • 左边群的阶: 根据 $\phi$ 函数的定义，$\#((\mathbb{Z}/nm\mathbb{Z})^*) = \phi(nm)$。
   • 右边群的阶: 直积群的阶等于其各分量群的阶的乘积。
   • $\#((\mathbb{Z}/n\mathbb{Z})^*) = \phi(n)$。
   • $\#((\mathbb{Z}/m\mathbb{Z})^*) = \phi(m)$。
   • 所以，$\#((\mathbb{Z}/n\mathbb{Z})^* \times (\mathbb{Z}/m\mathbb{Z})^* ) = \#((\mathbb{Z}/n\mathbb{Z})^*) \cdot \#((\mathbb{Z}/m\mathbb{Z})^*) = \phi(n)\phi(m)$。
   • 令两边相等: بما أن المجموعتين متماثلتان، فإن ترتيبهما متساوٍ.
   • 证明完毕。

这个推论是欧拉 $\phi$ 函数理论的顶峰。它给出了计算任意正整数 $n$ 的 $\phi(n)$ 值的通用公式。

1. 组合工具: 这个公式的推导依赖于我们之前建立的两个关键工具：
   • 工具 A (命题 1.4.7): 我们知道如何计算素数幂的 $\phi$ 值：$\phi(p^k) = p^{k-1}(p-1)$。
   • 工具 B (推论 1.5.7): 我们知道 $\phi$ 函数是积性的：若 $\operatorname{gcd}(n,m)=1$，则 $\phi(nm)=\phi(n)\phi(m)$。
2. 推导过程:
   • 第一步：分解。根据算术基本定理，任何一个大于 1 的整数 $n$ 都可以被唯一地分解为不同素数幂的乘积：$n = p_1^{a_1} p_2^{a_2} \cdots p_r^{a_r}$。
   • 第二步：应用积性。注意到 $p_1^{a_1}, p_2^{a_2}, \dots, p_r^{a_r}$ 这些项是两两互素的。因此，我们可以反复应用 $\phi$ 函数的积性性质：
   • 第三步：应用素数幂公式。现在我们对每一项 $\phi(p_i^{a_i})$ 应用工具 A：
   • 第四步：组合结果。将所有结果乘起来，就得到了最终的公式：
3. 另一种形式:
   • 公式 $\phi(n) = n \prod_{p|n}(1 - \frac{1}{p})$ 是等价的。
   • 推导:
   • 从 $\phi(p^k) = p^k - p^{k-1}$ 开始，提出 $p^k$：$\phi(p^k) = p^k(1 - \frac{p^{k-1}}{p^k}) = p^k(1 - \frac{1}{p})$。
   • 那么 $\phi(n) = \prod_i \phi(p_i^{a_i}) = \prod_i \left[ p_i^{a_i}(1-\frac{1}{p_i}) \right]$
   • $= (p_1^{a_1} p_2^{a_2} \cdots p_r^{a_r}) \cdot \left[ (1-\frac{1}{p_1})(1-\frac{1}{p_2})\cdots(1-\frac{1}{p_r}) \right]$
   • $= n \prod_{p|n} (1-\frac{1}{p})$。这里的 $\prod_{p|n}$ 表示对所有整除 $n$ 的不同素数 $p$ 进行连乘。

这个定理是一个非常深刻和重要的结论，是数论中的一个核心结果。

1. 定理的背景:
   • 我们已经看到，有些乘法群 $(\mathbb{Z}/n\mathbb{Z})^*$ 是循环的（如 $n=5, 7, 10$），有些不是（如 $n=8, 12$）。
   • 一个自然的问题是：到底哪些 $(\mathbb{Z}/n\mathbb{Z})^*$ 是循环群？
   • 这个定理给出了一个非常重要的肯定性结论：当模数 $p$ 是素数时，对应的乘法群 $(\mathbb{Z}/p\mathbb{Z})^*$ 总是循环群。
2. 定理内容:
   • 条件: $p$ 是一个素数。
   • 结论: 乘法群 $(\mathbb{Z}/p\mathbb{Z})^*$ 是一个循环群。
   • 同构关系: 任何一个阶为 $k$ 的循环群都同构于加法群 $\mathbb{Z}/k\mathbb{Z}$。
   • $(\mathbb{Z}/p\mathbb{Z})^*$ 的阶是 $\phi(p)=p-1$。
   • 因此，它同构于 $\mathbb{Z}/(p-1)\mathbb{Z}$。
3. 原根 (Primitive Root):
   • 一个循环群的生成元，在 $(\mathbb{Z}/p\mathbb{Z})^*$ 这个特定的群里，有一个特殊的名字，叫做“原根模 p”(primitive root modulo p)。
   • 所以，定理等价于说：对于任何素数 $p$，都存在原根模 $p$。
4. 证明的说明:
   • 原文明确指出，这个定理的证明比较复杂，将放在后续课程（第二部分）中。
   • 证明通常需要用到更多关于多项式在域上的根的性质，或者利用我们刚学过的恒等式 $\sum_{d|n}\phi(d)=n$。其思路大致是证明群中阶为 $d$ 的元素数量要么是 0 要么是 $\phi(d)$，然后利用该恒等式反推出阶为 $p-1$ 的元素（即生成元）数量是 $\phi(p-1) \ge 1$，从而证明其存在性。